123
题目 123
思路分析
啊？我又看错题了？
不是 蓝桥杯你在干什么
好吧 不是想象中的那么简单 这个数据范围
而且就是暴力构造出来做前缀和 好像也不是那么好构造
应该是要算循环节类似的用规律快速找到是第几组123……
我以为已经很妙了 结果只能过4个……6分 也还行
其实只差一步之遥了……基本分析到了 少了一个转换 有点可惜 但是能做到这里已经很不错了
数列中的每一个连续的部分可以看作一个小区间。
1 12 123 1234 12345 ...
每一个小区间都是一个 \(a_1=1\)、\(d=1\) 的等差数列，且区间的长度也能构成等差数列。
由于 \(l, r \le 10^{12}\)，即
所以最多有 1414214 个小区间构成该数列，满足任意 \(l, r\) 都能落在里面。
这意味着虽然我们不能直接查询某一位置的前缀和，但可以通过这些小区间来定位和计算某一位置的前缀和。
- 第 \(i\) 个区间的元素个数为 \(i\)。
- 定义 \(a[i]\) 表示前 \(i\) 个小区间的元素个数（\(1\sim n\) 的和）。则有：\(a[i]=a[i-1]+i\)。
- 定义 \(s[i]\) 表示前 \(i\) 个小区间的和。则有：\(s[i]=s[i-1]+a[i]\)。
- 对于数列中任意位置 \(i\)，一定存在一个最大的 \(j\) 满足 \(a[j]\le i\)，这表示第 \(i\) 个数落在第 \(j+1\) 区间内。
- 对于数列中任意位置 \(i\)，当它落在第 \(j+1\) 个区间，它是该区间第 \(k\) 个数，则它在数列中的前缀和为：\(s[j]+a[k]\)，其中 \(k=i-a[j]\)。
#include <iostream>
#define long long long
#define maxn 1414215
using namespace std;
long a[maxn], s[maxn];
long preSum(long i)
{
int l = 0, r = maxn, mid;
while (l < r)
{
mid = l + r + 1 >> 1;
if (a[mid] > i) r = mid - 1;
else l = mid;
}
return s[l] + a[i - a[l]];
}
int main()
{
for (int i = 1; i < maxn; i++)
{
a[i] = a[i - 1] + i;
s[i] = s[i - 1] + a[i];
}
int t;
scanf("%d", &t);
while (t--)
{
long l, r;
scanf("%lld%lld", &l, &r);
printf("%lld\n", preSum(r) - preSum(l - 1));
}
return 0;
}
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const int N=40010;
LL a[N],s[N];
int T;
LL find_group(LL x){
LL l=1,r=N;
while(l<r){
LL mid=(l+r)/2;
if(a[mid]>=x)
r=mid;
else
l=mid+1;
}
return r;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
for(int i=1;i<N;i++){
a[i]=((1+i)*i)/2;
s[i]=s[i-1]+a[i];
}
cin>>T;
while(T--){
LL L,R;cin>>L>>R;
auto gl=find_group(L);
LL idxl=gl-(a[gl]-L);
LL temp=0;
for(int i=1;i<idxl;i++) temp+=i;
LL sl=s[gl-1]+temp;
auto gr=find_group(R);
LL idxr=gr-(a[gr]-R);
temp=0;
for(int i=1;i<=idxr;i++) temp+=i;
LL sr=s[gr-1]+temp;
cout<<sr-sl<<endl;
}
return 0;
}
💬 评论